1. Field of Invention
The present invention relates generally to computer systems, and more particularly to a method and a system for accelerating return sequences by identifying pop-branch instruction sequences within a processor.
2. Relevant Background
Most programs executed by a processor include subroutines or procedures. Procedures are modules of code that are accessed by a procedure calling sequence. Once the procedure is finished, instruction execution is returned to the caller by the execution of a procedure return sequence.
Within some processor architectures, procedure call and return sequences may be compiled into a sequence of instructions. For example, a procedure calling sequence may consist of a PUSH instruction followed by a branch and link instruction. The PUSH instruction (or instructions) may save parameters used by instructions within the procedure onto the software stack. After the PUSH instruction, the processor may execute a branch and link instruction. The branch and link instruction causes instruction fetching and execution to begin at the starting address of the procedure and saves the address of the next sequential instruction following the branch and link instruction, known as the return or link address, in a link register. The link register may be a special purpose register or one of the general purpose registers (GPRs) used by the processor. Within the procedure, the link register contents are typically pushed onto the software stack so that its value is not overwritten if another procedure is called before returning to the original caller.
After the procedure finishes its function, the processor executes a procedure return sequence to resume instruction execution at the link address (the next sequential instruction address following the procedure calling instruction). Because the return address is often saved on the software stack, the procedure return sequence must first retrieve the return address from the software stack to use that address to determine the next group of instructions to be fetched.
A procedure return sequence may consist of one or more instructions. In some processor architectures a procedure return sequence may be a single instruction such as a POP or load instruction that can read the next return address from software stack and update the program counter (PC). Alternatively, the processor may use a POP or load instruction to read the link address from the software stack into an intermediate register, such as a GPR, before moving that value to the program counter to complete the procedure return sequence. In another illustrative example, the processor may determine that a return from a procedure may be an instruction moving the value saved in a link register (LR) into the PC. When the processor encounters any of these procedure return sequences after a procedure call, the processor jumps back to the next sequential instruction following the procedure calling instruction using the return address value retrieved from the software stack.
Additional logic may be added to the processor's hardware to improve the efficiency of instruction processing. For example, a link stack may be added to a processor's fetch logic to speed up instruction fetching. Those skilled in the art appreciate that a link stack may contain return addresses that may also exist on the software stack. However, the link stack operates independently from the software stack. Hardware logic associated with the link stack identifies procedure calls and returns. As procedure call instructions are identified prior to execution, the associated return address is loaded on to the link stack. Conversely, when procedure returns are identified, the associated return address is retrieved from the link stack and used to resume instruction fetching. Instead of waiting for instructions to execute and retrieving return addresses from the software stack, the processor may fetch instructions speculatively using addresses stored in the link stack.
As processors evolve, the procedure return sequence continues to change. In some processor architectures the procedure return may be comprised of multiple instructions. If the hardware logic supporting the link stack does not recognize these instructions as a procedure return sequence, return addresses may not retrieved from the link stack and as a result, the link stack may become out of sync with the instruction sequence. When the link stack becomes out of sync, the link stack may provide erroneous return address information which may cause multiple address mispredictions.